package test.bilibili;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @author chenyw
 * @date 2022/9/1 19:55
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n == 0 || n == 2) {
            System.out.println(n);
        }
        //动态规划
        int[] dp = new int[n + 1];
//            dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            boolean flag = true;
            int min = Integer.MAX_VALUE;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    flag = false;
                    min = Math.min(min, dp[j] + dp[i / j]);
                }
            }
            dp[i] = flag ? i : min;
        }
        System.out.println(dp[n]);
    }

}
